/*
  Using unordered_map. Compile with:
  g++ -o tix tickets2.cpp -std=c++0x
*/
#include <iostream>
#include <cstdlib>
#include <cerrno>
#include <algorithm>
#include <iterator>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <unordered_map>

using namespace std;

typedef set<string> string_set;
typedef vector<string> string_vector;
typedef pair<string,string> ticket;
typedef vector<ticket> ticket_vector;

string randomAirport() {
    string result;
    for( unsigned i = 0; i < 3; i++ ) {
	result += 'A' + ( rand() % 26 );
    }
    return result;
}

ostream &operator<<( ostream &o, ticket const &p) {
    return o << p.first << "->" << p.second;
}

void generate_airports_n( string_vector &v, unsigned n ) {
    string_set s;
    while ( s.size() < n ) s.insert( randomAirport() );
    copy( s.begin(), s.end(), back_inserter(v) );
}

void print_tickets( ticket_vector const &v ) {
    for ( ticket_vector::const_iterator it(v.begin()); v.end() != it; it++ ) {
	cout << *it << endl;
    }
}

ticket resolve( ticket_vector const &tix ) {
    typedef ticket_vector::const_iterator Iterator;
    typedef unordered_map<string,unsigned> Resolver;
    typedef Resolver::iterator RIterator;
    Resolver resolver;
    for( Iterator it(tix.begin()); tix.end() != it; it++ ) {
	{
	    RIterator found( resolver.find( it->first ) );
	    if ( resolver.end() == found ) {
		resolver.insert( make_pair( it->first, 2 ) );
	    } else { 
		resolver.erase(found); 
	    }
	}
	{
	    RIterator found( resolver.find( it->second ) );
	    if ( resolver.end() == found ) {
		resolver.insert( make_pair( it->second, 1 ) );
	    } else {
		resolver.erase(found);
	    }
	}
    }
    ticket result;
    assert( resolver.size() == 2 );
    for ( Resolver::iterator it(resolver.begin()); resolver.end() != it; it++ ) {
	if ( it->second & 2 ) result.first = it->first;
	if ( it->second & 1 ) result.second = it->first;
    }
    return result;
}

int main( int argc, char *argv[] ) {
    
    unsigned seed( argc > 1 ? 
		   strtol( argv[1], NULL, 10 ) : 
		   (unsigned)time(NULL) );
    if ( !seed || errno ) {
	cerr << "Bad seed." << endl;
	exit(0);
    }
    cout << "seed : " << seed << endl;
    srand( seed );

    string_vector airports;
    generate_airports_n( airports, 10 );

    vector<ticket> tickets;
    transform( airports.begin(), airports.end()-1,
	       airports.begin()+1, back_inserter(tickets),
	       make_pair<string,string> );

    print_tickets( tickets );
    const ticket answer(tickets.front().first, tickets.back().second );
    cout << "*" << answer << endl;
    cout << endl;
    random_shuffle( tickets.begin(), tickets.end() );
    print_tickets( tickets );
    cout << endl;

    const ticket resolved(resolve( tickets ));
    cout << "*" << resolved;
    assert( resolved == answer );
}
